package demo2;

import java.util.HashMap;
import java.util.Map;

public class Test {

    public void duplicateZeros(int[] arr) {

        //1.找到复写0的位置
        int cur = 0, dest = -1, n = arr.length;
        while (cur < n) {
            if (arr[cur] != 0) dest++;
            else dest += 2;
            if (dest >= n - 1) break;
            cur++;
        }
        //处理细节问题
        if (dest == n) {
            arr[n - 1] = 0;
            cur--;
            dest -= 2;
        }
        //从后向前复写
        while (cur >= 0) {
            if (arr[cur] != 0) {
                arr[dest--] = arr[cur--];
            }else {
                arr[dest--] = 0;
                arr[dest--] = 0;
                cur--;
            }
        }
    }

    public int totalFruit2(int[] fruits) {
        int n = fruits.length;
        int[] hash = new int[n + 1];
        int ret = 0;
        for (int left = 0, right = 0, kinds = 0; right < n; right++) {
            int in = fruits[right];
            if (hash[in] == 0) kinds++;
            hash[in]++; //进窗口
            while (kinds > 2) { //判断
                int out = fruits[left];
                hash[out]--; //出窗口
                if (hash[out] == 0) kinds--;
                left++;
            }
            ret = Math.max(ret, right - left + 1); //更新结果
        }
        return ret;
    }

    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> hash = new HashMap<>();
        int ret = 0;
        for (int left = 0, right = 0; right < fruits.length; right++) {
            int in = fruits[right];
            hash.put(in, hash.getOrDefault(in, 0) + 1); //进窗口
            while (hash.size() > 2) { //判断
                int out = fruits[left];
                hash.put(out, hash.get(out) - 1); //出窗口
                if (hash.get(out) == 0) {
                    hash.remove(out);
                }
                left++;
            }
            ret = Math.max(ret, right - left + 1); //更新结果
        }
        return ret;
    }

    /**
     * 移动零
     * @param nums
     */
    public void moveZeroes(int[] nums) {
        int n = nums.length;
        for (int cur = 0, dest = -1; cur < n; cur++) {
            if (nums[cur] != 0) {
                int tmp = nums[cur];
                nums[cur] = nums[dest + 1];
                nums[dest + 1] = tmp;
                dest++;
            }
        }
    }

    public static void main(String[] args) {

    }

}
